<?
include_once "SortHelper/SortHelper.php";
/**
 * ShuffleExp洗牌算法
 * 洗牌算法实际上就是常见的随机问题。我们可以抽象理解为：得到一个M以内的所有自然数的随机顺序数组。
 * 好的洗牌算法保证每一次的概率都基本一样
 * 
 */
class ShuffleExpRun{

    public $N;
    public $n;
    public $m;

    public function __construct($N, $n, $m)
    {
        $this->N = $N;
        $this->n = $n;
        $this->m = $m;
    }

    /**
     * 洗牌算法 - 自证函数主入口
     * 
     * 构建数据
     * 计算概率
     * 输出概率值
     */
    function ShuffleExpRun()
    {

        $freq = $arr = [];
        for ($i = 0; $i < $this->N; $i++) { 
            //构建数据
            $this->reset($arr);

            //洗牌算法
            $this->shuffle($arr);

            //统计每一位的总数量
            for ($j = 0; $j < $this->n; $j++) { 
               $freq[$j] += $arr[$j];
            }
        }
        //计算概率并输出
        for ($i=0; $i < $this->n; $i++) { 
            echo $i. "：". floatval($freq[$i] / $this->N) . "\n";
        }
    }

    /**
     * 构建数据
     */
    public function reset(&$arr)
    {
        //默认
        for ($i = 0; $i < $this->m; $i++) { 
            $arr[$i] = 1;
        }
        for ($i = $this->m; $i < $this->n; $i++) { 
            $arr[$i] = 0;
        }
    }

    /**
     * 洗牌算法 - 可单独使用此函数 - 放到这里是为了自证此函数真的是等概率算法
     * 从后往前排
     * 总数组长度 n, 初始化用 n - 1(因为数组索引从0开始)
     * 每次从 [0, i+1) 区间里随机选择一个元素和 i 位置的进行交换
     */
    public function shuffle(&$arr)
    {
        for ($i = $this->n - 1; $i >= 0; $i--) {
            //从 [0, i+1) 区间里随机选择一个元素
            $x = intval($this->randomFloat() * ($i+1));
            SortHelper::swap($arr, $i, $x);
        }
    }

    /**
     * 辅助函数
     * 生成 min - max 之间的随机数（float）带小数
     * 如果都不传，默认生成 0 - 1 之间的随机数
     * 
     */
    function randomFloat($min = 0, $max = 1) {
        return $min + mt_rand() / mt_getrandmax() * ($max - $min);
    }
    
}


$shuff = new ShuffleExpRun(100000,10,5);
$shuff->ShuffleExpRun();
